#include <iostream>
#include <string>
#include <vector>
#include <windows.h>

using namespace std;

// KMP 算法理解起来比较费劲，本篇需要数学理论支撑才能看懂代码
// 这里展示的代码基本是将阮一峰这篇文章中的计算过程翻译为程序代码，文章地址：https://kb.cnblogs.com/page/176818/

// @pattern 表示模式参数(待查找的字符串)
vector<int> getNext(const wstring &pattern) {
    const int len = pattern.length();
    // next 数组默认全部填充 0
    vector<int> next(len, 0);
    int j = 0;
    wstring leftStr = L"", rightStr = L"";
    // 这里只需要从第二个元素计算相关的 next 匹配表
    for (int i = 1; i < pattern.length(); i++) {
        j = 0;
        while (j < i) {
            // 优先匹配最长前缀和后缀
            // substr (startPos,endPos)  , 位置截取区间：【 startPos，截取个数）
            leftStr = pattern.substr(0, i - j);  // 左侧字符串，表示可能的前缀
            rightStr = pattern.substr(j + 1, i - j);  // 右侧字符串，表示可能的后缀
            if (leftStr == rightStr) {
                //  cout << "索引：" << i << ", left: " << leftStr << " rightIndex:" << j + 1 << ",  right: " << rightStr << endl;
                next[i] = leftStr.length();
                break;
            }
            j++;
        }
    }
    return next;
}

// @origin 原始字符串
// @pattern 模式字符串(需要寻找的字符串)
int findStr(wstring origin, wstring pattern) {
    vector<int> next = getNext(pattern);
    //  搜索模式字符在目标字符中的位置
    int j = 0;
    int hasCommonStrNum = 0;  // 公共字符个数

    for (int i = 0; i < origin.length();) {
        if (origin.at(i) == pattern.at(j)) {
            j++;
        } else if (j > 0) {
            hasCommonStrNum = next[j - 1];
            j = 0;
            // 这里和阮一峰文章计算偏移量有差异，文章是将模式字符串右移动，
            // 代码里面我们是将原始字符串左移，而模式字符串始终保持不动
            i = i - hasCommonStrNum;
            continue;
        } else {
            // j==0的情况就是第一个字符匹配失败了
            j = 0;
        }
        i++;
        if (j == pattern.length()) {
//            cout << "匹配成功,匹配区间：[ " << i - pattern.length() << " , " << i << " ) , 目标字符串：" << pattern << endl;  // 左闭右开区间
            return i - pattern.length();
        }
    }

    return -1;
}

int main() {
    wstring str = L"c++/go/cangjie/编程语言 - 文本搜索性能大比拼，谁才是字符串比较的性能王者？请看2024年度性能测试野榜排名——c++/go/cangjie/编程语言";
    wstring text = L"";
    int num = 1000000;  // 100万行文本

    for (int i = 0; i < num; i++) {
        if (i % 2 == 0) {
            //偶数行不追加换行符，保持前后有相同字符串，kmp算法匹配指定字符串时，就会跳过公共前缀，便于测试算法的性能，否则就跟普通的BF算法没有区别了
            // text.WriteString(str)
            text += str;
        } else {
            // 文本后面 + 数字编号，保证每一行都是不同的
            text += L"\n" + str + to_wstring(i) + L"\n";
        }
    }
    // 设置最后一行为固定字符串，方便我们查找
    wstring lastRowStr = str + to_wstring(num + 1);
    text += lastRowStr;
    int pos = -1;
    // ↑↑↑  以上构建待处理的字符串过程放置在本次文本比较时间之间之外 ，我们本次只是测试文本比较性能 ↑↑↑

    DWORD startSec = GetTickCount();
    // 开始查找最后一行
    int loopCount = 10;
    for (int i = 0; i < loopCount; i++) {
        pos = findStr(text, lastRowStr);
    }

    DWORD useMs = (GetTickCount() - startSec) / 10;

    cout << "100万文本字符串查找目标字符串(KMP算法)，字符串位置：" << pos << " 单次耗时(ms): " << useMs << endl;

    return 0;
}
